/*
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *
 * 冒泡排序（Bubble Sort）
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *
 *  只操作相邻的两个数据
 *  每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换
 *  一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *
 *  是原地排序算法，空间复杂度 O(1)
 *  是稳定的排序算法：如果元素相同，不会交换位置
 *  时间复杂度
 *    - 最好：O(n)，有序
 *    - 最坏：O(n * n)，倒序
 *    - 平均：O(n * n)
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *
 * Tips: 排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了
 *       累计交换次数为逆序度: 逆序度 = 满有序度 - 有序度
 *
 *       冒泡排序包含两种操作，一种是元素的比较，一种是元素的交换
 *       交换次数是固定的，等于逆序度，无论怎么优化都不会改变
 *       比较次数是可以优化的
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *
 * Author：LiuXin
 * Email：2315496341@qq.com
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 */

//  初始版本(升序)
function bubbleSort1(arr) {
  let len = arr.length

  // 1轮冒泡至少确定未排序中1个数字的正确位置 n个数需要n-1轮即可完成全部排序（最后一轮不用比较）
  // 每一轮对比的序列是所有未确位置的元素 即： [0, 总长度 - 当前轮数 - 1]
  // 如果当前元素大于它后边的元素，则交换位置

  for (let i = 0; i < len; i++) {
    console.log(
      `第${i + 1}轮 · 共${len}轮 · 总长度${len} · 序列范围[0, ${len - 1 - i})`
    )
    for (let j = 0; j < len - 1 - i; j++) {
      console.log(arr[j], arr[j + 1])
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
    console.log("-----------------")
  }

  return arr
}

//  优化版本
function bubbleSort(arr) {
  let len = arr.length
  let _changeCount = 0 // 交换了多少次[测试变量]

  // 1轮冒泡至少确定未排序中1个数字的正确位置 n个数需要n次冒泡即可完成全部排序
  // 每一轮对比的序列是所有未确位置的元素 即： [0, 总长度 - 当前轮数 - 1]
  // 如果当前元素大于它后边的元素，则交换位置

  // 优化：
  // 如果当前这一轮冒泡没有元素交换位置，则表明数组已经有序

  for (let i = 0; i < len; i++) {
    console.log(
      `第${i + 1}轮 · 共${len}轮 · 总长度${len} · 排序范围[0, ${len - 1 - i})`
    )

    let flag = true // 当前轮是否已经达到有序状态

    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        console.log(`交换 => ${arr[j]}-${arr[j + 1]} => 待交换序列:`, [...arr])

        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        flag = false // 有数据交换 状态为无序

        _changeCount++ // 累计交换次数[测试变量]
      }
    }

    console.log(
      `\n当前轮状态为：${flag ? "有序" : "无序"}${
        flag ? " · 共交换了" + _changeCount + "次" : ""
      }`
    )
    console.log("-----------------")

    if (flag) break
  }

  return arr
}

/**
 * Test Case
 */
{
  function test() {
    let args = []
    let i = Math.ceil(Math.random() * 6)
    while (i--) {
      // i 个元素
      args.push(parseInt(Math.random() * 200))
    }
    console.log([...args], "===>", bubbleSort(args))
  }

  // 完全正序
  bubbleSort([1, 2, 3])
  // 完全倒序

  bubbleSort([9, 8, 7])

  // 10 组测试
  let times = 10
  while (times--) {
    console.log(
      `\n\n-------------------------------- · ${times} · --------------------------------\n\n`
    )
    test()
  }
}
